package com.mengfou.binarysearch;

/**
 * @author mengfou
 */
public class FindLocalMinimumValue {

    /**
     * 查找数组中的局部最小值
     * @param arr 待查找数组
     * @return 局部最小值
     */
    public int localMinimum(int[] arr) {
        int len = 0;
        if (arr == null || (len = arr.length) == 0 || len < 2) return -1;
        // 首尾边界情况
        if (arr[0] < arr[1]) return 0;
        if (arr[len - 1] < arr[len - 2]) return len - 1;

        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid >= 1 && mid < len - 1 &&
                    arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) { // 当前满足局部最小值
                return mid;
            } else if (mid >= 1 && arr[mid] > arr[mid - 1]) { // 局部最小值在左侧
                right = mid - 1;
            } else if (mid < len - 1 && arr[mid] > arr[mid + 1]) { // 局部最小值在右侧
                left = mid + 1;
            }
        }
        return -1;
    }
}
